package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * LCP 24. 数字游戏
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/3 9:57
 */
public class NumsGame {

    public static void main(String[] args) {
        NumsGame test = new NumsGame();

        // [0,0,0,5,6,7]
//        int[] arr = {3, 4, 5, 1, 6, 7};

        // [0,0,0,0,0]
//        int[] arr = {1, 2, 3, 4, 5};

        // [0,1,2,3,3,3]

        //
        int[] arr = Utils.getArr(10000, 1, 1000);

        int[] ints = test.numsGame(arr);
        System.out.println(Arrays.toString(ints));
    }

    public int[] numsGame(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            nums[i] += length - i;
        }
        long ac = 0;
        long bc = 0;
        PriorityQueue<Integer> as = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        PriorityQueue<Integer> bs = new PriorityQueue<>();
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            as.add(num);
            ac += num;
            if (as.size() - 2 == bs.size()) {
                int v = as.poll();
                ac -= v;
                bs.add(v);
                bc += v;
            } else {
                if (!bs.isEmpty() && as.peek() > bs.peek()) {
                    int av = as.poll();
                    int bv = bs.poll();
                    bs.add(av);
                    as.add(bv);
                    ac -= av;
                    ac += bv;
                    bc -= bv;
                    bc += av;
                }
            }
            long mid = as.peek();
            arr[i] = (int) ((mid * as.size() - ac + bc - mid * bs.size()) % 1000000007);
        }
        return arr;
    }

}
